SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Chan's algorithm</title>

</head>

Chan's algorithm

</h1>

</header>

In <a href="Computational_geometry" title="Computational geometry">computational geometry</a>, Chan's algorithm,<a href="#cite_note-Chan96-1">[1]</a> named after <a href="Timothy_M._Chan" title="Timothy M. Chan">Timothy M. Chan</a>, is an optimal <a href="Output-sensitive_algorithm" title="Output-sensitive algorithm">output-sensitive algorithm</a> to compute the <a href="Convex_hull" title="Convex hull">convex hull</a> of a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> points, in 2- or 3-dimensional space.

The algorithm takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy"> time, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> algorithm (<a href="Graham_scan" title="Graham scan">Graham scan</a>, for example) with <a href="Jarvis_march" class="mw-redirect" title="Jarvis march">Jarvis march</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nh)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(nh)}</annotation>

</semantics>

</math><img src="./a83b89fe12283915f8ec586b55536fad81b62a8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.316ex; height:2.843ex;" alt="{\displaystyle O(nh)}" loading="lazy">), in order to obtain an optimal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy"> time. Chan's algorithm is notable because it is much simpler than the <a href="Kirkpatrick%E2%80%93Seidel_algorithm" title="Kirkpatrick–Seidel algorithm">Kirkpatrick–Seidel algorithm</a>, and it naturally extends to 3-dimensional space. This paradigm<a href="#cite_note-2">[2]</a> has been independently developed by Frank Nielsen in his Ph.D. thesis.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Overview">Overview</h3></div>

A single pass of the algorithm requires a parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> which is between 0 and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> (number of points of our set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">). Ideally, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=h}</annotation>

</semantics>

</math><img src="./83027e6ec2f7c7af6c516d4ac76d0af7f27addc4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.478ex; height:2.176ex;" alt="{\displaystyle m=h}" loading="lazy"> but <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">, the number of vertices in the output convex hull, is not known at the start. Multiple passes with increasing values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> are done which then terminates when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\geq h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\geq h}</annotation>

</semantics>

</math><img src="./ef262d2ccf530dc1a73c0ff8b6fbcef757499cad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.478ex; height:2.343ex;" alt="{\displaystyle m\geq h}" loading="lazy">(see below on choosing parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">).

The algorithm starts by arbitrarily partitioning the set of points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K=\lceil n/m\rceil }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K=\lceil n/m\rceil }</annotation>

</semantics>

</math><img src="./e21c4214fe93956ae2cb5f62a70808ddb6e8e51c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.827ex; height:2.843ex;" alt="{\displaystyle K=\lceil n/m\rceil }" loading="lazy"> subsets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (Q_{k})_{k=1,2,...K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (Q_{k})_{k=1,2,...K}}</annotation>

</semantics>

</math><img src="./45ac4f256364b91ed62ec26dd92435b05976ce06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.495ex; height:3.009ex;" alt="{\displaystyle (Q_{k})_{k=1,2,...K}}" loading="lazy"> with at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> points each; notice that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K=O(n/m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K=O(n/m)}</annotation>

</semantics>

</math><img src="./bd7847014a07e264457324dd0e7f4710b6ba712d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.345ex; height:2.843ex;" alt="{\displaystyle K=O(n/m)}" loading="lazy">.

For each subset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{k}}</annotation>

</semantics>

</math><img src="./2fa6cb6cf7ffc157202e52dd5711e755892d1015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.927ex; height:2.509ex;" alt="{\displaystyle Q_{k}}" loading="lazy">, it computes the convex hull, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{k}}</annotation>

</semantics>

</math><img src="./1a0887b56787ba96e79de2b9f5c6ff30aabad1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.751ex; height:2.509ex;" alt="{\displaystyle C_{k}}" loading="lazy">, using an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(p\log p)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(p\log p)}</annotation>

</semantics>

</math><img src="./bfb164a1199f2f6abe86d0ebf247e04f87294cb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.667ex; height:2.843ex;" alt="{\displaystyle O(p\log p)}" loading="lazy"> algorithm (for example, <a href="Graham_scan" title="Graham scan">Graham scan</a>), where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> is the number of points in the subset. As there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m)}</annotation>

</semantics>

</math><img src="./a0ffd498cf521ce19814e6b7053f1f8ebb1d3c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.623ex; height:2.843ex;" alt="{\displaystyle O(m)}" loading="lazy"> points each, this phase takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K\cdot O(m\log m)=O(n\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K\cdot O(m\log m)=O(n\log m)}</annotation>

</semantics>

</math><img src="./2ad8931b530dfdcc2452a97d6b224a838caec337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.016ex; height:2.843ex;" alt="{\displaystyle K\cdot O(m\log m)=O(n\log m)}" loading="lazy"> time.

During the second phase, <a href="Gift_wrapping_algorithm" title="Gift wrapping algorithm">Jarvis's march</a> is executed, making use of the precomputed (mini) convex hulls, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C_{k})_{k=1,2,...K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C_{k})_{k=1,2,...K}}</annotation>

</semantics>

</math><img src="./6ea52056966713ff46189b0a67ed732f87370f7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.319ex; height:3.009ex;" alt="{\displaystyle (C_{k})_{k=1,2,...K}}" loading="lazy">. At each step in this Jarvis's march algorithm, we have a point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}}</annotation>

</semantics>

</math><img src="./5bab39399bf5424f25d957cdc57c84a0622626d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.059ex; height:2.009ex;" alt="{\displaystyle p_{i}}" loading="lazy"> in the convex hull (at the beginning, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}}</annotation>

</semantics>

</math><img src="./5bab39399bf5424f25d957cdc57c84a0622626d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.059ex; height:2.009ex;" alt="{\displaystyle p_{i}}" loading="lazy"> may be the point in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> with the lowest y coordinate, which is guaranteed to be in the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">), and need to find a point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}=f(p_{i},P)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}=f(p_{i},P)}</annotation>

</semantics>

</math><img src="./40dd4e9f52dc5a92c25c2e91564de580fbc7a77a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:15.094ex; height:2.843ex;" alt="{\displaystyle p_{i+1}=f(p_{i},P)}" loading="lazy"> such that all other points of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> are to the right of the line <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}p_{i+1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}p_{i+1}}</annotation>

</semantics>

</math><img src="./29ce276fcd8eb76fc98a7e873a13f9f592340f95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.128ex; height:2.009ex;" alt="{\displaystyle p_{i}p_{i+1}}" loading="lazy">, where the notation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}=f(p_{i},P)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}=f(p_{i},P)}</annotation>

</semantics>

</math><img src="./40dd4e9f52dc5a92c25c2e91564de580fbc7a77a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:15.094ex; height:2.843ex;" alt="{\displaystyle p_{i+1}=f(p_{i},P)}" loading="lazy"> simply means that the next point, that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation>

</semantics>

</math><img src="./9577169925aad488f2b57f47eb556b22f89be6e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}" loading="lazy">, is determined as a function of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}}</annotation>

</semantics>

</math><img src="./5bab39399bf5424f25d957cdc57c84a0622626d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.059ex; height:2.009ex;" alt="{\displaystyle p_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">. The convex hull of the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{k}}</annotation>

</semantics>

</math><img src="./2fa6cb6cf7ffc157202e52dd5711e755892d1015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.927ex; height:2.509ex;" alt="{\displaystyle Q_{k}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{k}}</annotation>

</semantics>

</math><img src="./1a0887b56787ba96e79de2b9f5c6ff30aabad1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.751ex; height:2.509ex;" alt="{\displaystyle C_{k}}" loading="lazy">, is known and contains at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> points (listed in a clockwise or counter-clockwise order), which allows to compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(p_{i},Q_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(p_{i},Q_{k})}</annotation>

</semantics>

</math><img src="./fefe631fac9f4a81427675dc7a941eb0068906db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.018ex; height:2.843ex;" alt="{\displaystyle f(p_{i},Q_{k})}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log m)}</annotation>

</semantics>

</math><img src="./01cc8bc56e37299e3f7da69f923f11e601030fd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.982ex; height:2.843ex;" alt="{\displaystyle O(\log m)}" loading="lazy"> time by <a href="Binary_search" title="Binary search">binary search</a>. Hence, the computation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(p_{i},Q_{k})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(p_{i},Q_{k})}</annotation>

</semantics>

</math><img src="./fefe631fac9f4a81427675dc7a941eb0068906db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.018ex; height:2.843ex;" alt="{\displaystyle f(p_{i},Q_{k})}" loading="lazy"> for all the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> subsets can be done in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(K\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(K\log m)}</annotation>

</semantics>

</math><img src="./49bc31e36a2ab5ccd2af6b31b37e3bddc22a018f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.435ex; height:2.843ex;" alt="{\displaystyle O(K\log m)}" loading="lazy"> time. Then, we can determine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(p_{i},P)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(p_{i},P)}</annotation>

</semantics>

</math><img src="./c5a176b9dfd8bff5cfd683a70b08a06c364bef9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.836ex; height:2.843ex;" alt="{\displaystyle f(p_{i},P)}" loading="lazy"> using the same technique as normally used in Jarvis's march, but only considering the points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}</annotation>

</semantics>

</math><img src="./8abecfe44674caeb1565c005d90c6eff8628b576.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.756ex; height:2.843ex;" alt="{\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}" loading="lazy"> (i.e. the points in the mini convex hulls) instead of the whole set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">. For those points, one iteration of Jarvis's march is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(K)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(K)}</annotation>

</semantics>

</math><img src="./21d6095b24973251be0d4d45dc1699053877217a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.649ex; height:2.843ex;" alt="{\displaystyle O(K)}" loading="lazy"> which is negligible compared to the computation for all subsets. Jarvis's march completes when the process has been repeated <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(h)}</annotation>

</semantics>

</math><img src="./08b2b7b64f0a9e9848ecd3a114cc7dcc8ca6179d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.922ex; height:2.843ex;" alt="{\displaystyle O(h)}" loading="lazy"> times (because, in the way Jarvis march works, after at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> iterations of its outermost loop, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> is the number of points in the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">, we must have found the convex hull), hence the second phase takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(Kh\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(Kh\log m)}</annotation>

</semantics>

</math><img src="./7c8338a8fa3964c4be628b41b70a1401cd34c72b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.774ex; height:2.843ex;" alt="{\displaystyle O(Kh\log m)}" loading="lazy"> time, equivalent to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy"> time if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is close to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> (see below the description of a strategy to choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> such that this is the case).

By running the two phases described above, the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> points is computed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy"> time.

<div class="mw-heading mw-heading3"><h3 id="Choosing_the_parameter_m">Choosing the parameter m</h3></div>

If an arbitrary value is chosen for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, it may happen that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m<h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m<h}</annotation>

</semantics>

</math><img src="./919a0a20d885f1c5d13df805a5fa64d3ad2e7e64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.478ex; height:2.176ex;" alt="{\displaystyle m<h}" loading="lazy">. In that case, after <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> steps in the second phase, we interrupt the <a href="Gift_wrapping_algorithm" title="Gift wrapping algorithm">Jarvis's march</a> as running it to the end would take too much time.

At that moment, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log m)}</annotation>

</semantics>

</math><img src="./682cdba436d9a0d65dba5410e350bb5670a005b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.764ex; height:2.843ex;" alt="{\displaystyle O(n\log m)}" loading="lazy"> time will have been spent, and the convex hull will not have been calculated.

The idea is to make multiple passes of the algorithm with increasing values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">; each pass terminates (successfully or unsuccessfully) in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log m)}</annotation>

</semantics>

</math><img src="./682cdba436d9a0d65dba5410e350bb5670a005b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.764ex; height:2.843ex;" alt="{\displaystyle O(n\log m)}" loading="lazy"> time. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> increases too slowly between passes, the number of iterations may be large; on the other hand, if it rises too quickly, the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> for which the algorithm terminates successfully may be much larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">, and produce a complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log m)>O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log m)>O(n\log h)}</annotation>

</semantics>

</math><img src="./4c1847ad6a68665b619c13daf2fbc4e3962e1399.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.924ex; height:2.843ex;" alt="{\displaystyle O(n\log m)>O(n\log h)}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Squaring_Strategy">Squaring Strategy</h4></div>

One possible strategy is to square the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> at each iteration, up to a maximum value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> (corresponding to a partition in singleton sets).<a href="#cite_note-4">[4]</a> Starting from a value of 2, at iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=\min \left(n,2^{2^{t}}\right)}">

<mrow>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=\min \left(n,2^{2^{t}}\right)}</annotation>

</semantics>

</math><img src="./7cd2c063c7e05a31867d8204ae79c0b6478c8d56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:17.468ex; height:4.843ex;" alt="{\displaystyle m=\min \left(n,2^{2^{t}}\right)}" loading="lazy"> is chosen. In that case, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log h)}</annotation>

</semantics>

</math><img src="./a9aa9ccc0c7ea09bafb8c5e999273d0cb9262b84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.639ex; height:2.843ex;" alt="{\displaystyle O(\log \log h)}" loading="lazy"> iterations are made, given that the algorithm terminates once we have

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=2^{2^{t}}\geq h\iff \log \left(2^{2^{t}}\right)\geq \log h\iff 2^{t}\geq \log h\iff \log {2^{t}}\geq \log {\log h}\iff t\geq \log {\log h},}</annotation>

</semantics>

</math><img src="./40d3ea6b19a06afb8d992c7bdf36f45c6bc2712a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:95.363ex; height:4.843ex;" alt="{\displaystyle m=2^{2^{t}}\geq h\iff \log \left(2^{2^{t}}\right)\geq \log h\iff 2^{t}\geq \log h\iff \log {2^{t}}\geq \log {\log h}\iff t\geq \log {\log h},}" loading="lazy"></dd></dl>

with the logarithm taken in base <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">, and the total running time of the algorithm is

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{t=0}^{\lceil \log \log h\rceil }O\left(n\log \left(2^{2^{t}}\right)\right)=O(n)\sum _{t=0}^{\lceil \log \log h\rceil }2^{t}=O\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)=O(n\log h).}</annotation>

</semantics>

</math><img src="./c6da8ef994876a3f531fdcae67d986516f5c9cde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:77.115ex; height:7.676ex;" alt="{\displaystyle \sum _{t=0}^{\lceil \log \log h\rceil }O\left(n\log \left(2^{2^{t}}\right)\right)=O(n)\sum _{t=0}^{\lceil \log \log h\rceil }2^{t}=O\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)=O(n\log h).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="In_three_dimensions">In three dimensions</h3></div>

To generalize this construction for the 3-dimensional case, an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> algorithm to compute the 3-dimensional convex hull by Preparata and Hong should be used instead of Graham scan, and a 3-dimensional version of Jarvis's march needs to be used. The time complexity remains <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy">.<a href="#cite_note-Chan96-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Pseudocode">Pseudocode</h3></div>

In the following pseudocode, text between parentheses and in italic are comments. To fully understand the following pseudocode, it is recommended that the reader is already familiar with <a href="Graham_scan" title="Graham scan">Graham scan</a> and <a href="Gift_wrapping_algorithm" title="Gift wrapping algorithm">Jarvis march</a> algorithms to compute the convex hull, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, of a set of points,

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.

<dl><dd>Input: Set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> points .</dd>

<dd>Output: Set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> points, the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.</dd></dl>

<dl><dd><dl><dd>(Pick a point of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> which is guaranteed to be in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">: for instance, the point with the lowest y coordinate.)</dd>

<dd>(This operation takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> time: e.g., we can simply iterate through <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}:=PICK\_START(P)}</annotation>

</semantics>

</math><img src="./bb13c2f6c7cc90a431deaa39837b5edcdb07c377.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:25.804ex; height:2.843ex;" alt="{\displaystyle p_{1}:=PICK\_START(P)}" loading="lazy"></dd></dl></dd></dl>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{0}}</annotation>

</semantics>

</math><img src="./2b969ada68a88e2aeba9a2d2096abaf1fd53c21d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{0}}" loading="lazy"> is used in the Jarvis march part of this Chan's algorithm,</dd>

<dd>so that to compute the second point, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy">, in the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{0}}</annotation>

</semantics>

</math><img src="./2b969ada68a88e2aeba9a2d2096abaf1fd53c21d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{0}}" loading="lazy"> is not a point of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<dd>(For more info, see the comments close to the corresponding part of the Chan's algorithm.)</dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{0}:=(-\infty ,0)}</annotation>

</semantics>

</math><img src="./7230be1064060a02d8ec319dca5cd0a3b2fc847e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:14.196ex; height:2.843ex;" alt="{\displaystyle p_{0}:=(-\infty ,0)}" loading="lazy"></dd></dl></dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">, the number of points in the final convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">, is not known.)</dd>

<dd>(These are the iterations needed to discover the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, which is an estimate of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">.)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\leq m}</annotation>

</semantics>

</math><img src="./95082613925e098474ec31f0d0979247d7989b92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.478ex; height:2.343ex;" alt="{\displaystyle h\leq m}" loading="lazy"> is required for this Chan's algorithm to find the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<dd>(More specifically, we want <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\leq m\leq h^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\leq m\leq h^{2}}</annotation>

</semantics>

</math><img src="./ea4320408b11c5b90b03d2b289adf350ffe86a14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.97ex; height:2.843ex;" alt="{\displaystyle h\leq m\leq h^{2}}" loading="lazy">, so that not to perform too many unnecessary iterations</dd>

<dd>and so that the time complexity of this Chan's algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log h)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log h)}</annotation>

</semantics>

</math><img src="./a9470a317308c81039cf1f67c67273fee318e81d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.139ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log h)}" loading="lazy">.)</dd>

<dd>(As explained above in this article, a strategy is used where at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log \log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log \log n}</annotation>

</semantics>

</math><img src="./18c8ce21e650a468af0acd8f3895322ecddb7efb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.112ex; height:2.509ex;" alt="{\displaystyle \log \log n}" loading="lazy"> iterations are required to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">.)</dd>

<dd>(Note: the final <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> may not be equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">, but it is never smaller than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> and greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h^{2}}</annotation>

</semantics>

</math><img src="./0ee96b2a49abab22ea200cc66ab956379d0c4773.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.393ex; height:2.676ex;" alt="{\displaystyle h^{2}}" loading="lazy">.)</dd>

<dd>(Nevertheless, this Chan's algorithm stops once <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> iterations of the outermost loop are performed,</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\neq h}</annotation>

</semantics>

</math><img src="./25be27bcefa9fc4c9ea7144555038b55c69ad231.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.478ex; height:2.676ex;" alt="{\displaystyle m\neq h}" loading="lazy">, it doesn't perform <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> iterations of the outermost loop.)</dd>

<dd>(For more info, see the Jarvis march part of this algorithm below, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is returned if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}==p_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}==p_{1}}</annotation>

</semantics>

</math><img src="./fe4d3eb947b0442eed8b1ff82150bef7304380b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:11.289ex; height:2.009ex;" alt="{\displaystyle p_{i+1}==p_{1}}" loading="lazy">.)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq t\leq \log \log n}</annotation>

</semantics>

</math><img src="./428c13c58a2d2159b498867efffc135b5e27dbc2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.311ex; height:2.509ex;" alt="{\displaystyle 1\leq t\leq \log \log n}" loading="lazy"> do

<dl><dd>(Set parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> for the current iteration. A "squaring scheme" is used as described above in this article.</dd>

<dd>There are other schemes: for example, the "doubling scheme", where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=2^{t}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=2^{t}}</annotation>

</semantics>

</math><img src="./5fcdce95c3ca530cb1c1e7a25fcc51561fbcaa9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.127ex; height:2.509ex;" alt="{\displaystyle m=2^{t}}" loading="lazy">, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }</annotation>

</semantics>

</math><img src="./0acb6bd42d450c2cb736f4b6b116069743977f83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.041ex; height:2.843ex;" alt="{\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }" loading="lazy">.</dd>

<dd>If the "doubling scheme" is used, though, the resulting time complexity of this Chan's algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log ^{2}h)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log ^{2}h)}</annotation>

</semantics>

</math><img src="./fe5d944a174d50eb2568e95f78a9e808ed402b7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.193ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\log ^{2}h)}" loading="lazy">.)</dd>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m:=2^{2^{t}}}</annotation>

</semantics>

</math><img src="./9cd2f66d71a3d48776255b05b0cb890c12cb4cf1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.649ex; height:3.009ex;" alt="{\displaystyle m:=2^{2^{t}}}" loading="lazy"></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd>(Initialize an empty list (or array) to store the points of the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">, as they are found.)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C:=()}</annotation>

</semantics>

</math><img src="./672ef052cefd91640b62ccec813e27f01aa7693c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.321ex; height:2.843ex;" alt="{\displaystyle C:=()}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ADD(C,p_{1})}</annotation>

</semantics>

</math><img src="./09f4d2e8523771fd51da0a27a1b4eb87ebe62c46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.425ex; height:2.843ex;" alt="{\displaystyle ADD(C,p_{1})}" loading="lazy"></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd>(Arbitrarily split set of points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }</annotation>

</semantics>

</math><img src="./26b7241e0fb00153504a8c40e33824b1908dfe8a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.496ex; height:4.843ex;" alt="{\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }" loading="lazy"> subsets of roughly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> elements each.)</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}:=SPLIT(P,m)}</annotation>

</semantics>

</math><img src="./6d04af7b3de4356e2df9d4936a273cb2d0368881.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.539ex; height:2.843ex;" alt="{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}:=SPLIT(P,m)}" loading="lazy"></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd>(Compute the convex hull of all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> subsets of points, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}</annotation>

</semantics>

</math><img src="./07991e28db04e7cbcc29bc61625ff627164d21bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.529ex; height:2.509ex;" alt="{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}" loading="lazy">.)</dd>

<dd>(It takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}</annotation>

</semantics>

</math><img src="./ca449d8a72ed995fb14985d506b5dcbfd32fe8fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.491ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}" loading="lazy"> time.)</dd>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\leq h^{2}}</annotation>

</semantics>

</math><img src="./e3edb19c40b160771c7e601b97e37c120d7fffae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.532ex; height:2.843ex;" alt="{\displaystyle m\leq h^{2}}" loading="lazy">, then the time complexity is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}">

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}</annotation>

</semantics>

</math><img src="./24b268f1c1bf4555c25813dc9279ab270b02597d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.43ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}" loading="lazy">.)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq k\leq K}</annotation>

</semantics>

</math><img src="./3229ff22b7f6ad15424c311b4afded2386201fea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.637ex; height:2.343ex;" alt="{\displaystyle 1\leq k\leq K}" loading="lazy"> do

<dl><dd>(Compute the convex hull of subset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{k}}</annotation>

</semantics>

</math><img src="./2fa6cb6cf7ffc157202e52dd5711e755892d1015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.927ex; height:2.509ex;" alt="{\displaystyle Q_{k}}" loading="lazy">, using Graham scan, which takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(m\log m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(m\log m)}</annotation>

</semantics>

</math><img src="./ac6b0f8e9c22761d05da3593fe86323bdb4134fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.486ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(m\log m)}" loading="lazy"> time.)</dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{k}}</annotation>

</semantics>

</math><img src="./1a0887b56787ba96e79de2b9f5c6ff30aabad1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.751ex; height:2.509ex;" alt="{\displaystyle C_{k}}" loading="lazy"> is the convex hull of the subset of points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{k}}</annotation>

</semantics>

</math><img src="./2fa6cb6cf7ffc157202e52dd5711e755892d1015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.927ex; height:2.509ex;" alt="{\displaystyle Q_{k}}" loading="lazy">.)</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{k}:=GRAHAM\_SCAN(Q_{k})}</annotation>

</semantics>

</math><img src="./ac2ca1d77483357bfeb33f69e8cbde5a20eae6a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.05ex; height:2.843ex;" alt="{\displaystyle C_{k}:=GRAHAM\_SCAN(Q_{k})}" loading="lazy"></dd></dl></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd>(At this point, the convex hulls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{1},C_{2},\dots ,C_{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{1},C_{2},\dots ,C_{K}}</annotation>

</semantics>

</math><img src="./6d60df4750dc1a35032afa40188e683e9d357c6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.999ex; height:2.509ex;" alt="{\displaystyle C_{1},C_{2},\dots ,C_{K}}" loading="lazy"> of respectively the subsets of points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}</annotation>

</semantics>

</math><img src="./07991e28db04e7cbcc29bc61625ff627164d21bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.529ex; height:2.509ex;" alt="{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}" loading="lazy"> have been computed.)</dd>

<dd>(Now, use a modified version of the Jarvis march algorithm to compute the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<dd>(Jarvis march performs in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(nh)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(nh)}</annotation>

</semantics>

</math><img src="./4ebf6649527d3721b66d4d5eb1bbc7fafcc992e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.393ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(nh)}" loading="lazy"> time, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the number of input points and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> is the number of points in the convex hull.)</dd>

<dd>(Given that Jarvis march is an <a href="Output-sensitive_algorithm" title="Output-sensitive algorithm">output-sensitive algorithm</a>, its running time depends on the size of the convex hull, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">.)</dd>

<dd>(In practice, it means that Jarvis march performs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> iterations of its outermost loop.</dd>

<dd>At each of these iterations, it performs at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> iterations of its innermost loop.)</dd>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\leq m\leq h^{2}}</annotation>

</semantics>

</math><img src="./ea4320408b11c5b90b03d2b289adf350ffe86a14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.97ex; height:2.843ex;" alt="{\displaystyle h\leq m\leq h^{2}}" loading="lazy">, so we do not want to perform more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> iterations in the following outer loop.)</dd>

<dd>(If the current <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is smaller than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">, i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m<h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m<h}</annotation>

</semantics>

</math><img src="./919a0a20d885f1c5d13df805a5fa64d3ad2e7e64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.478ex; height:2.176ex;" alt="{\displaystyle m<h}" loading="lazy">, the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> cannot be found.)</dd>

<dd>(In this modified version of Jarvis march, we perform an operation inside the innermost loop which takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log m)}</annotation>

</semantics>

</math><img src="./d5dbdd29081dc0e48e19418f809ef6a2cebe84d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.058ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log m)}" loading="lazy"> time.</dd>

<dd>Hence, the total time complexity of this modified version is</dd>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(mK\log m)={\mathcal {O}}(m\left\lceil {\frac {n}{m}}\right\rceil \log m)={\mathcal {O}}(n\log m)={\mathcal {O}}(n\log 2^{2^{t}})={\mathcal {O}}(n2^{t}).}</annotation>

</semantics>

</math><img src="./22732ee13e528fbb8b5bec5a26c5c22162a89d3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:73.343ex; height:4.843ex;" alt="{\displaystyle {\mathcal {O}}(mK\log m)={\mathcal {O}}(m\left\lceil {\frac {n}{m}}\right\rceil \log m)={\mathcal {O}}(n\log m)={\mathcal {O}}(n\log 2^{2^{t}})={\mathcal {O}}(n2^{t}).}" loading="lazy"></dd>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\leq h^{2}}</annotation>

</semantics>

</math><img src="./e3edb19c40b160771c7e601b97e37c120d7fffae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.532ex; height:2.843ex;" alt="{\displaystyle m\leq h^{2}}" loading="lazy">, then the time complexity is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}">

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}</annotation>

</semantics>

</math><img src="./24b268f1c1bf4555c25813dc9279ab270b02597d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.43ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}" loading="lazy">.)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m}</annotation>

</semantics>

</math><img src="./be7492673ec3919cb5774b3ba4bb81a7c2365c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq m}" loading="lazy"> do</dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd><dl><dd>(Note: here, a point in the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is already known, that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy">.)</dd></dl></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd><dl><dd>(In this inner for loop, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> possible next points to be on the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}</annotation>

</semantics>

</math><img src="./39e33b9712f2cfab9e3afa4137d41f04ed63d66a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.199ex; height:2.343ex;" alt="{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}" loading="lazy">, are computed.)</dd>

<dd>(Each of these <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> possible next points is from a different <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{k}}</annotation>

</semantics>

</math><img src="./1a0887b56787ba96e79de2b9f5c6ff30aabad1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.751ex; height:2.509ex;" alt="{\displaystyle C_{k}}" loading="lazy">:</dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{i,k}}</annotation>

</semantics>

</math><img src="./f9d9d78f74e58323e549f73a9bae0d07bc7e1fb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.151ex; height:2.343ex;" alt="{\displaystyle q_{i,k}}" loading="lazy"> is a possible next point on the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> which is part of the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{k}}</annotation>

</semantics>

</math><img src="./1a0887b56787ba96e79de2b9f5c6ff30aabad1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.751ex; height:2.509ex;" alt="{\displaystyle C_{k}}" loading="lazy">.)</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}</annotation>

</semantics>

</math><img src="./39e33b9712f2cfab9e3afa4137d41f04ed63d66a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.199ex; height:2.343ex;" alt="{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}" loading="lazy"> depend on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">: that is, for each iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> possible next points to be on the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<dd>(Note: at each iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, only one of the points among <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}</annotation>

</semantics>

</math><img src="./39e33b9712f2cfab9e3afa4137d41f04ed63d66a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.199ex; height:2.343ex;" alt="{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}" loading="lazy"> is added to the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq k\leq K}</annotation>

</semantics>

</math><img src="./3229ff22b7f6ad15424c311b4afded2386201fea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.637ex; height:2.343ex;" alt="{\displaystyle 1\leq k\leq K}" loading="lazy"> do

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle JARVIS\_BINARY\_SEARCH}</annotation>

</semantics>

</math><img src="./60a64a20e575514fc7eff8b007c448b78009c2d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:32.653ex; height:2.176ex;" alt="{\displaystyle JARVIS\_BINARY\_SEARCH}" loading="lazy"> finds the point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\in C_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\in C_{k}}</annotation>

</semantics>

</math><img src="./f1ab31df9662e3839f28773e83d7e7aea4bf4514.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.807ex; height:2.509ex;" alt="{\displaystyle d\in C_{k}}" loading="lazy"> such that the angle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \measuredangle p_{i-1}p_{i}d}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \measuredangle p_{i-1}p_{i}d}</annotation>

</semantics>

</math><img src="./cf5164c6dce3e881a975c9f570363bdd7538c852.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.933ex; height:2.509ex;" alt="{\displaystyle \measuredangle p_{i-1}p_{i}d}" loading="lazy"> is maximized ,</dd>

<dd>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \measuredangle p_{i-1}p_{i}d}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \measuredangle p_{i-1}p_{i}d}</annotation>

</semantics>

</math><img src="./cf5164c6dce3e881a975c9f570363bdd7538c852.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.933ex; height:2.509ex;" alt="{\displaystyle \measuredangle p_{i-1}p_{i}d}" loading="lazy"> is the angle between the vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}">

<mover>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}</annotation>

</semantics>

</math><img src="./21b5be2ed60ae171f9b1959cf8701bf3b7706940.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.024ex; margin-top: -0.34ex; width:6.193ex; height:3.509ex;" alt="{\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\overrightarrow {p_{i}d}}}">

<mover>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overrightarrow {p_{i}d}}}</annotation>

</semantics>

</math><img src="./0efefa54ed345bc18f73ea1fb663a3872ef400b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.024ex; margin-top: -0.423ex; width:3.344ex; height:4.176ex;" alt="{\displaystyle {\overrightarrow {p_{i}d}}}" loading="lazy">. Such <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> is stored in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{i,k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{i,k}}</annotation>

</semantics>

</math><img src="./f9d9d78f74e58323e549f73a9bae0d07bc7e1fb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.151ex; height:2.343ex;" alt="{\displaystyle q_{i,k}}" loading="lazy">.)</dd>

<dd>(Angles do not need to be calculated directly: the <a href="Curve_orientation" title="Curve orientation">orientation test</a> can be used .)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle JARVIS\_BINARY\_SEARCH}</annotation>

</semantics>

</math><img src="./60a64a20e575514fc7eff8b007c448b78009c2d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:32.653ex; height:2.176ex;" alt="{\displaystyle JARVIS\_BINARY\_SEARCH}" loading="lazy"> can be performed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log m)}</annotation>

</semantics>

</math><img src="./d5dbdd29081dc0e48e19418f809ef6a2cebe84d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.058ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log m)}" loading="lazy"> time.)</dd>

<dd>(Note: at the iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1}</annotation>

</semantics>

</math><img src="./9fb857369fbc28dab4b5d76bb835e6f196b1d1cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i=1}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}</annotation>

</semantics>

</math><img src="./59e173464efeca694de388b55b0e67e1e00f6678.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:20.717ex; height:2.843ex;" alt="{\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> is known and is a point in the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">:</dd>

<dd>in this case, it is the point of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> with the lowest y coordinate.)</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{i,k}:=JARVIS\_BINARY\_SEARCH(p_{i-1},p_{i},C_{k})}</annotation>

</semantics>

</math><img src="./bd142240df22e8a66f465915769d927133a46e43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:52.216ex; height:3.009ex;" alt="{\displaystyle q_{i,k}:=JARVIS\_BINARY\_SEARCH(p_{i-1},p_{i},C_{k})}" loading="lazy"></dd></dl></dd></dl></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd><dl><dd>(Choose the point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}</annotation>

</semantics>

</math><img src="./61f3087237ea4110f6171398f852a7a17176f132.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.453ex; height:3.009ex;" alt="{\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}" loading="lazy"> which maximizes the angle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \measuredangle p_{i-1}p_{i}z}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \measuredangle p_{i-1}p_{i}z}</annotation>

</semantics>

</math><img src="./188af33198f769db023d18d0d38b8aee006fc18c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.805ex; height:2.509ex;" alt="{\displaystyle \measuredangle p_{i-1}p_{i}z}" loading="lazy"> to be the next point on the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.)</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}:=JARVIS\_NEXT\_CH\_POINT(p_{i-1},p_{i},(q_{i,1},q_{i,2},\dots ,q_{i,K}))}</annotation>

</semantics>

</math><img src="./6a1d5737d6a1604bc17960d8a72b62a175c67668.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:68.429ex; height:3.009ex;" alt="{\displaystyle p_{i+1}:=JARVIS\_NEXT\_CH\_POINT(p_{i-1},p_{i},(q_{i,1},q_{i,2},\dots ,q_{i,K}))}" loading="lazy"></dd></dl></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd><dl><dd>(Jarvis march terminates when the next selected point on the convext hull, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation>

</semantics>

</math><img src="./9577169925aad488f2b57f47eb556b22f89be6e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}" loading="lazy">, is the initial point, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy">.)</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}==p_{1}}</annotation>

</semantics>

</math><img src="./fe4d3eb947b0442eed8b1ff82150bef7304380b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:11.289ex; height:2.009ex;" alt="{\displaystyle p_{i+1}==p_{1}}" loading="lazy">

<dl><dd>(Return the convex hull of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> which contains <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=h}</annotation>

</semantics>

</math><img src="./ace14f68f8bd734935930f29e501834c08238956.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.24ex; height:2.176ex;" alt="{\displaystyle i=h}" loading="lazy"> points.)</dd>

<dd>(Note: of course, no need to return <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation>

</semantics>

</math><img src="./9577169925aad488f2b57f47eb556b22f89be6e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}" loading="lazy"> which is equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy">.)</dd>

<dd>return <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}</annotation>

</semantics>

</math><img src="./80870d5273d9dd4ad0457a8a62eedb01956c66cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.95ex; height:2.843ex;" alt="{\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}" loading="lazy"></dd></dl></dd>

<dd>else

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ADD(C,p_{i+1})}</annotation>

</semantics>

</math><img src="./a50db41c87184ab41441f73df7354cb3ca42f3cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.271ex; height:2.843ex;" alt="{\displaystyle ADD(C,p_{i+1})}" loading="lazy"></dd></dl></dd></dl></dd></dl></dd></dl></dd></dl>

<dl><dd><dl><dd><dl><dd>(If after <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> iterations a point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}}</annotation>

</semantics>

</math><img src="./9577169925aad488f2b57f47eb556b22f89be6e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:4.159ex; height:2.009ex;" alt="{\displaystyle p_{i+1}}" loading="lazy"> has not been found so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i+1}==p_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i+1}==p_{1}}</annotation>

</semantics>

</math><img src="./fe4d3eb947b0442eed8b1ff82150bef7304380b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:11.289ex; height:2.009ex;" alt="{\displaystyle p_{i+1}==p_{1}}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m<h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m<h}</annotation>

</semantics>

</math><img src="./919a0a20d885f1c5d13df805a5fa64d3ad2e7e64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.478ex; height:2.176ex;" alt="{\displaystyle m<h}" loading="lazy">.)</dd>

<dd>(We need to start over with a higher value for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">.)</dd></dl></dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2></div>

Chan's paper contains several suggestions that may improve the practical performance of the algorithm, for example:

<ul><li>When computing the convex hulls of the subsets, eliminate the points that are not in the convex hull from consideration in subsequent executions.</li>

<li>The convex hulls of larger point sets can be obtained by merging previously calculated convex hulls, instead of recomputing from scratch.</li>

<li>With the above idea, the dominant cost of algorithm lies in the pre-processing, i.e., the computation of the convex hulls of the groups. To reduce this cost, we may consider reusing hulls computed from the previous iteration and merging them as the group size is increased.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2></div>

Chan's paper contains some other problems whose known algorithms can be made optimal output sensitive using his technique, for example:

<ul><li>Computing the <a href="Lower_envelope" title="Lower envelope">lower envelope</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(S)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(S)}</annotation>

</semantics>

</math><img src="./f714d72d451d361bf34e900c39d43ddb9a4c162f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.891ex; height:2.843ex;" alt="{\displaystyle L(S)}" loading="lazy"> of a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> line segments, which is defined as the lower boundary of the unbounded <a href="Trapezoid" title="Trapezoid">trapezoid</a> of formed by the intersections.</li>

<li>Hershberger<a href="#cite_note-5">[5]</a> gave an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> algorithm which can be sped up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy">, where h is the number of edges in the envelope</li></ul>

<ul><li>Constructing output sensitive algorithms for higher dimensional convex hulls. With the use of grouping points and using efficient data structures, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log h)}</annotation>

</semantics>

</math><img src="./0c63f97b78aa80f7496c81e17afca572454dd3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.062ex; height:2.843ex;" alt="{\displaystyle O(n\log h)}" loading="lazy"> complexity can be achieved provided h is of polynomial order in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.</li></ul>

<ul><li><a href="Convex_hull_algorithms" title="Convex hull algorithms">Convex hull algorithms</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChan1996" class="citation journal cs1">Chan, Timothy M. (1996). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02712873">"Optimal output-sensitive convex hull algorithms in two and three dimensions"</a>. <a href="Discrete_%26_Computational_Geometry" title="Discrete & Computational Geometry">Discrete & Computational Geometry</a>. 16 (4): 361–368. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02712873">10.1007/BF02712873</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFNielsen2000" class="citation book cs1">Nielsen, Frank (2000). "Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms". Discrete and Computational Geometry. Lecture Notes in Computer Science. Vol. 1763. pp. 250–257. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-46515-7_21">10.1007/978-3-540-46515-7_21</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-67181-7</bdi>.</cite>

</li>

Frank Nielsen. "<a rel="nofollow" class="external text" href="http://hal.inria.fr/tel-00832414/">Adaptive Computational Geometry</a>".

Ph.D. thesis, <a href="INRIA" class="mw-redirect" title="INRIA">INRIA</a>, 1996.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFChazelleMatoušek1995" class="citation journal cs1"><a href="Bernard_Chazelle" title="Bernard Chazelle">Chazelle, Bernard</a>; <a href="Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)" title="Jiří Matoušek (mathematician)">Matoušek, Jiří</a> (1995). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0925-7721%2894%2900018-Q">"Derandomizing an output-sensitive convex hull algorithm in three dimensions"</a>. <a href="Computational_Geometry_(journal)" title="Computational Geometry (journal)">Computational Geometry</a>. 5: 27–32. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0925-7721%2894%2900018-Q">10.1016/0925-7721(94)00018-Q</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFHershberger1989" class="citation journal cs1">Hershberger, John (1989). "Finding the upper envelope of n line segments in O(n log n) time". <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>. 33 (4): 169–174. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2889%2990136-1">10.1016/0020-0190(89)90136-1</a>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-29" href="https://en.wikipedia.org/wiki/?title=Chan's_algorithm&oldid=1288029234">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>